home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 11 / Cream of the Crop 11-1.iso / games / ted5.zip / IGRABSRC.ZIP / JHUFF.BAK < prev    next >
Text File  |  1993-02-04  |  8KB  |  426 lines
  1. /**************************************************************
  2.     JHUFF.C -- A rle/huffman Data Compression Program
  3. **************************************************************/
  4.  
  5. #include "igrab.h"
  6. #pragma hdrstop
  7.  
  8. unsigned char huge *infile,
  9.           huge *outfile;
  10.  
  11. long inlength,outlength;
  12.  
  13. long counts[256];
  14.  
  15. unsigned huffbits[256];
  16. unsigned long huffstring[256];
  17.  
  18. huffnode nodearray[256];    // 256 nodes is worst case
  19.  
  20. /*
  21. =============================================================================
  22.  
  23.                COMPRESSION SUBS
  24.  
  25. =============================================================================
  26. */
  27.  
  28.  
  29.  
  30. /*
  31. ======================
  32. =
  33. = CountBytes
  34. =
  35. = Adds the bytes in the pointed to area to the counts array
  36. = If this is the first segment, make sure counts is zerod
  37. =
  38. ======================
  39. */
  40.  
  41. void CountBytes (unsigned char huge *start, long length)
  42. {
  43.   long i;
  44.  
  45.   while (length--)
  46.     counts[*start++]++;
  47. }
  48.  
  49. /*
  50. =======================
  51. =
  52. = FindLeast
  53. =
  54. = Returns the byte with the lowest counts value
  55. =
  56. =======================
  57. */
  58.  
  59. int FindLeast (void)
  60. {
  61.   int i,least;
  62.   long low = 0x7fffffff;
  63.  
  64.   for (i=0;i<256;i++)
  65.     if (counts[i]<low)
  66.     {
  67.       low = counts[i];
  68.       least = i;
  69.     }
  70.  
  71.   return least;
  72. }
  73.  
  74. /*========================================================================*/
  75.  
  76. /*
  77. ==================
  78. =
  79. = TraceNode
  80. =
  81. = A recursive function that follows all leaves of nodearray and fills in
  82. = coding tables huffbits and huffstring.
  83. =
  84. ==================
  85. */
  86.  
  87. void TraceNode (int nodenum,int numbits,unsigned long bitstring)
  88. {
  89.   unsigned bit0,bit1;
  90.  
  91.   bit0 = nodearray[nodenum].bit0;
  92.   bit1 = nodearray[nodenum].bit1;
  93.  
  94.   numbits++;
  95.  
  96.  
  97.   if (bit0 <256)
  98.   {
  99.     huffbits[bit0]=numbits;
  100.     huffstring[bit0]=bitstring;        // just added a zero in front
  101.   }
  102.   else
  103.   {
  104.     if (numbits<24)            // if the string is this long, its 0
  105.       TraceNode (bit0-256,numbits,bitstring);
  106.   }
  107.  
  108.   if (bit1 <256)
  109.   {
  110.     huffbits[bit1]=numbits;
  111.     huffstring[bit1]=bitstring+ (1ul<<(numbits-1));    // add a one in front
  112.     if (huffbits[bit1]>24 && counts[bit1])
  113.     {
  114.       puts("Error: Huffman bit string went over 32 bits!");
  115.       exit(1);
  116.     }
  117.   }
  118.   else
  119.   {
  120.     if (numbits<24)            // if the string is this long, its 0
  121.      TraceNode (bit1-256,numbits,bitstring+(1ul<<(numbits-1)));
  122.   }
  123. }
  124.  
  125.  
  126. /*
  127. =======================
  128. =
  129. = Huffmanize
  130. =
  131. = Takes the counts array and builds a huffman tree at
  132. = nodearray, then builds a codeing table.
  133. = 
  134. =======================
  135. */
  136.  
  137. void Huffmanize (void)
  138. {
  139. //
  140. // codes are either bytes if <256 or nodearray numbers+256 if >=256
  141. //
  142.   unsigned value[256],code0,code1;
  143. //
  144. // probablilities are the number of times the code is hit or $ffffffff if
  145. // it is allready part of a higher node
  146. //
  147.   unsigned long prob[256],low,workprob;
  148.  
  149.   int i,worknode,bitlength;
  150.   unsigned long bitstring;
  151.  
  152.   memset(huffstring,0,sizeof(huffstring));
  153.   memset(huffbits,0,sizeof(huffbits));
  154.  
  155. //
  156. // all possible leaves start out as bytes
  157. //
  158.   for (i=0;i<256;i++)
  159.   {
  160.     value[i]=i;
  161.     prob[i]=counts[i];
  162.   }
  163.  
  164. //
  165. // start selecting the lowest probable leaves for the ends of the tree
  166. //
  167.  
  168.   worknode = 0;
  169.   while (1)    // break out of when all codes have been used
  170.   {
  171.     //
  172.     // find the two lowest probability codes
  173.     //
  174.  
  175.     code0=0xffff;
  176.     low = 0x7ffffffff;
  177.     for (i=0;i<256;i++)
  178.       if (prob[i]<low)
  179.       {
  180.     code0 = i;
  181.     low = prob[i];
  182.       }
  183.  
  184.     code1=0xffff;
  185.     low = 0x7fffffff;
  186.     for (i=0;i<256;i++)
  187.       if (prob[i]<low && i != code0)
  188.       {
  189.     code1 = i;
  190.     low = prob[i];
  191.       }
  192.  
  193.     if (code1 == 0xffff)
  194.     {
  195.       if (value[code0]<256)
  196.     errout("Weirdo huffman error: last code wasn't a node!");
  197.       if (value[code0]-256 != 254)
  198.     errout("Weirdo huffman error: headnode wasn't 254!");
  199.       break;
  200.     }
  201.  
  202.     //
  203.     // make code0 into a pointer to work
  204.     // remove code1 (make 0xffffffff prob)
  205.     //
  206.     nodearray[worknode].bit0 = value[code0];
  207.     nodearray[worknode].bit1 = value[code1];
  208.  
  209.     value[code0] = 256 + worknode;
  210.     prob[code0] += prob[code1];
  211.     prob[code1] = 0xffffffff;
  212.     worknode++;
  213.   }
  214.  
  215. //
  216. // done with tree, now build table recursively
  217. //
  218.  
  219.   TraceNode (254,0,0);
  220.  
  221. }
  222.  
  223. /*========================================================================*/
  224.  
  225. /*
  226. ===============
  227. =
  228. = OptimizeNodes
  229. =
  230. = Goes through a huffman table and changes the 256-511 node numbers to the
  231. = actular address of the node.  Must be called before HuffExpand
  232. =
  233. ===============
  234. */
  235.  
  236. void OptimizeNodes (huffnode *table)
  237. {
  238.   huffnode *node;
  239.   int i;
  240.  
  241.   node = table;
  242.  
  243.   for (i=0;i<255;i++)
  244.   {
  245.     if (node->bit0 >= 256)
  246.       node->bit0 = (unsigned)(table+(node->bit0-256));
  247.     if (node->bit1 >= 256)
  248.       node->bit1 = (unsigned)(table+(node->bit1-256));
  249.     node++;
  250.   }
  251. }
  252.  
  253. /*========================================================================*/
  254.  
  255. /*
  256. ======================
  257. =
  258. = HuffCompress
  259. =
  260. = The file must be counted with CountBytes and then Huffmanized first
  261. =
  262. ======================
  263. */
  264.  
  265. #if 0
  266. long HuffCompress (unsigned char huge *source, long length,
  267.   unsigned char huge *dest)
  268. {
  269.   long outlength;
  270.   unsigned long string;
  271.   unsigned biton,bits;
  272.   unsigned char byte;
  273.  
  274.   outlength = biton = 0;
  275.  
  276.   *(long huge *)dest=0;        // so bits can be or'd on
  277.  
  278.   while (length--)
  279.   {
  280.     byte = *source++;
  281.     bits = huffbits[byte];
  282.     string = huffstring[byte] << biton;
  283.     *(long huge *)(dest+1)=0;    // so bits can be or'd on
  284.     *(long huge *)dest |= string;
  285.     biton += bits;        // advance this many bits
  286.     dest+= biton/8;
  287.     biton&=7;            // stay under 8 shifts
  288.     outlength+=bits;
  289.   }
  290.  
  291.   return (outlength+7)/8;
  292. }
  293. #endif
  294.  
  295. /*========================================================================*/
  296.  
  297. /*
  298. ======================
  299. =
  300. = HuffExpand
  301. =
  302. ======================
  303. */
  304.  
  305. void HuffExpand (unsigned char huge *source, unsigned char huge *dest,
  306.   long length,huffnode *hufftable)
  307. {
  308.   unsigned bit,byte,node,code;
  309.   unsigned sourceseg,sourceoff,destseg,destoff,endseg,endoff;
  310.   huffnode *nodeon,*headptr;
  311.  
  312.   nodeon = headptr = hufftable+254;    // head node is allways node 254
  313.  
  314.   bit = 1;
  315.   byte = *source++;
  316.  
  317.   while (length)
  318.   {
  319.     if (byte&bit)
  320.       code = nodeon->bit1;
  321.     else
  322.       code = nodeon->bit0;
  323.  
  324.     bit<<=1;
  325.     if (bit==256)
  326.     {
  327.       bit=1;
  328.       byte = *source++;
  329.     }
  330.  
  331.     if (code<256)
  332.     {
  333.       *dest++=code;
  334.       nodeon=headptr;
  335.       length--;
  336.     }
  337.     else
  338.       nodeon = (huffnode *)code;
  339.   }
  340.  
  341.  
  342. #if 0
  343.  
  344.   source++;    // normalize
  345.   source--;
  346.   dest++;
  347.   dest--;
  348.  
  349.   sourceseg = FP_SEG(source);
  350.   sourceoff = FP_OFF(source);
  351.   destseg = FP_SEG(dest);
  352.   destoff = FP_OFF(dest);
  353.  
  354.   length--;
  355. //
  356. // al = source byte
  357. // cl = bit in source (1,2,4,8,...)
  358. // dx = code
  359. //
  360. // ds:si source
  361. // es:di dest
  362. // ss:bx node pointer
  363. //
  364.  
  365. asm     mov    bx,headptr
  366. asm    mov    cl,1
  367.  
  368. asm    mov    si,sourceoff
  369. asm    mov    di,destoff
  370. asm    mov    es,destseg
  371. asm    mov    ds,sourceseg
  372.  
  373. asm    lodsb            // load first byte
  374.  
  375. expand:
  376. asm    test    al,cl        // bit set?
  377. asm    jnz    bit1
  378. asm    mov    dx,ss:bx    // take bit0 path from node
  379. asm    jmp    gotcode
  380. bit1:
  381. asm    mov    dx,ss:bx+2    // take bit1 path
  382.  
  383. gotcode:
  384. asm    shl    cl,1        // advance to next bit position
  385. asm    jnc    sourceup
  386. asm    lodsb
  387. asm    cmp    si,0x10        // normalize ds:si
  388. asm      jb    sinorm
  389. asm    mov    cx,ds
  390. asm    inc    cx
  391. asm    mov    ds,cx
  392. asm    xor    si,si
  393. sinorm:
  394. asm    mov    cl,1        // back to first bit
  395.  
  396. sourceup:
  397. asm    or    dh,dh        // if dx<256 its a byte, else move node
  398. asm    jz    storebyte
  399. asm    mov    bx,dx        // next node = (huffnode *)code
  400. asm    jmp    expand
  401.  
  402. storebyte:
  403. asm    mov    [es:di],dl
  404. asm    inc    di        // write a decopmpressed byte out
  405. asm    mov    bx,headptr    // back to the head node for next bit
  406.  
  407. asm    cmp    di,0x10        // normalize es:di
  408. asm      jb    dinorm
  409. asm    mov    dx,es
  410. asm    inc    dx
  411. asm    mov    es,dx
  412. asm    xor    di,di
  413. dinorm:
  414.  
  415. asm    sub    WORD PTR ss:length,1
  416. asm    jnc    expand
  417. asm      dec    WORD PTR ss:length+2
  418. asm    jns    expand        // when length = ffff ffff, done
  419.  
  420. asm    mov    ax,ss
  421. asm    mov    ds,ax
  422.  
  423. #endif
  424.  
  425. }
  426.